package com.base.bst;

import java.util.NoSuchElementException;
import java.util.TreeMap;

/**
 * @author leon
 * @Description: TODO(二叉搜索树)
 * @date 2022年04月24日 13:50
 */
public class BST {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root;
    int size = 0;

    public BST(int val) {
        root = new TreeNode(val);
        size++;
    }

    public BST() {

    }

    /**
     * 查找是否存在值为val的结点
     *
     * @param val
     * @return
     */
    public boolean contains(int val) {
        TreeNode node = contains(this.root, val);
        return node != null;
    }

    public TreeNode contains(TreeNode root, int val) {
        if (root == null) {
            return null;
        } else if (root.val == val) {
            return root;
        } else if (val < root.val) {
            return contains(root.left, val);
        } else {
            return contains(root.right, val);
        }
    }

    public TreeNode add(int val) {
        root = add(root, val);
        return root;
    }

    public TreeNode add(TreeNode root, int val) {
        if (root == null) {
            size++;
            return new TreeNode(val);
        } else if (val < root.val) {
            root.left = add(root.left, val);
        } else if (val > root.val) {
            root.right = add(root.right, val);
        }
        return root;
    }

    public TreeNode minNode(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public TreeNode removeMin(TreeNode root) {
        if (root.left == null) {
            TreeNode right = root.right;
            root.right = null;
            root = null;
            size--;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    public int removeMin(){
        TreeNode treeNode = removeMin(root);
        return treeNode.val;
    }

    public TreeNode maxNode(TreeNode root) {
        while (root.right != null) {
            root = root.right;
        }
        return root;
    }
    public int removeMax(){
        TreeNode treeNode = removeMax(root);
        return  treeNode.val;
    }

    public TreeNode removeMax(TreeNode root) {
        if (root.right == null) {
            TreeNode left = root.left;
            root.left = null;
            root = null;
            size--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    /**
     * 删除指定值的结点
     *
     * @param val
     * @return
     */
    public TreeNode remove(TreeNode root, int val) {
        if (root == null) {
            throw new NoSuchElementException("没有这个元素");
        } else if (val < root.val) {
            root.left = remove(root.left, val);
            return root;
        } else if (val > root.val) {
            root.right = remove(root.right, val);
            return root;
        } else {
            if(root.left==null){
                TreeNode right = root.right;
                root.right =null;
                root = null;
                return right;

            }else if(root.right==null){
                TreeNode left = root.left;
                root.left = null;
                root = null;
                return left;
            }else {
                TreeNode minMax = minNode(root.right);
                removeMax(root.right);
                minMax.right = root.right;
                minMax.left = root.left;
                root.left=root.right=root=null;
                return minMax;
            }
        }
    }


    public int remove(int val){
        TreeNode remove = remove(root, val);
        return  remove.val;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        toSting(builder, root);
        return builder.toString();
    }

    public void toSting(StringBuilder stringBuilder, TreeNode root) {
        if (root == null) {
            return;
        }
        toSting(stringBuilder, root.left);
        stringBuilder.append(root.val);
        toSting(stringBuilder, root.right);

    }

    public int getSize() {
        return size;
    }



    public static void main(String[] args) {
        BST bst = new BST();
        bst.add(5);
        bst.add(1);
        bst.add(3);
        bst.add(4);
        bst.add(6);
        System.out.println(bst.toString());
        bst.remove(3);
        System.out.println(bst.toString());
        bst.remove(4);
        System.out.println(bst.toString());

    }

}
